package 并查集;

/**
 * @author shy_black
 * @date 2019/4/22 16:14
 * @Description: quick union快速集合
 *
 */
public class UnionFind_2 implements UnionFind {
    private int[] parent;
    private int[] sz;

    public UnionFind_2(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }


    @Override
    public int getSize() {
        return parent.length;
    }

    //查找过程，查找元素p对应的集合编号
    //O(h)复杂度，h为树的高度
    private int find(int p) {
        if (p < 0 && p >= parent.length) {
            throw new IllegalArgumentException("非法下标");
        }
        while (p != parent[p]) {
            //如果p ！= parent[p],让p等于parent[p],不断寻找p的根
            p = parent[p];
        }
        return p;
    }

    //查看p和q是否所属一个集合
    //O(h)复杂度，h为树的高度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;
        //如果p的节点数小于q的节点数，
        // 让p的根节点指向q的根节点
        if (sz[pRoot] < sz[qRoot]) {

            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];

        }
    }
}
